Scheduling programs have gained considerable popularity among project-oriented professions such as product engineering companies, construction firms, and manufacturing plants. Scheduling programs allow a project manager to organize and track the development of a project. In the most general sense, a scheduling program operates by receiving an input of project-related information, generating a schedule based on this information, and then graphically or in a tabular manner, displaying the details concerning the status of the project, projected completion date, anticipated delays, etc.
The critical path method (CPM) of scheduling is used in a significant number of scheduling programs. CPM scheduling generally operates by receiving a list of tasks, each task having varying restrictions or constraints, and generating a schedule based on the task restrictions or constraints. More specifically, a set of tasks are provided to the scheduling program. Each task represents a specific job or discrete amount of work that must be performed on a project. Additionally, each task has a set of restrictions or constraints which dictate when and how long the task should be performed. To generate a meaningful schedule, CPM scheduling requires the input of information which identifies when each task is to be performed. This information can be provided by specifying constraints such as: a start date and a finish date, a start date and a task duration, a task duration and a finish date, or a task duration and a start or finish date which is dependent upon another task. If this information is not specified, the typical CPM scheduling program will assume the start date for each task to be the current date, and the duration of the task will default to a specific granularity such as one day, one week, etc.
Linking information concerning one or more of the tasks may also be entered. For instance, if a project consists of three tasks (Task 1, Task 2, and Task 3), the user may specify that Task 1 must be completed before Task 2 and Task 2 must be completed before Task 3. This information can be provided in the form of entering a start date for Task 2, which is equivalent to the finish date for Task 1, or by specifying that the start date for Task 2 is dependent upon the completion of Task 1. The latter method is referred to as a link.
Once the user enters the task information, a CPM scheduling program generates a schedule based on the provided task constraints. This is accomplished by performing a forward pass in which each task is examined. At the completion of the forward pass, a schedule is created that starts on the start date of the first task that can be scheduled and satisfies all of the provided task constraints. Next, the critical path for the project is determined. The critical path can be defined as the longest duration path through the network of task dependencies. The critical path is calculated by performing a backward pass from the last finish date to the earliest start date.
CPM scheduling programs are most beneficial for projects in which the tasks have dependencies on each other. Because of this, they are well suited for product-oriented projects which inherently have tasks that must be performed in a specific order. As an example, in building a house, the tasks of laying a foundation, framing the house, and shingling the roofing must be performed in this order. There are, however, many situations where the order of performing certain tasks of a project are arbitrary. For instance, in publishing a news letter, the order in which the articles are written is arbitrary. CPM scheduling programs typically do not produce meaningful results when the tasks do not have dependencies. As an example, if the three tasks (Task 1, Task 2 and Task 3) are not required to be performed in any specific order (i.e., do not have any dependencies), a CPM scheduling program will generate a “flat schedule” as illustrated in Schedule Example 1.
Schedule Example 1|----Task 1-----||----Task 2----------------------||----Task 3----------------------|
The problems associated with flat scheduling are evident when the tasks are viewed with respect to the resources assigned to the tasks. For instance, if a single resource is assigned to each of these three tasks, the flat schedule indicates that the resource will be required to work on three tasks at the same time. This results in “overloading” the resource. Alternatively, separate resources (Resource 1, Resource 2 and Resource 3) could be assigned to each of the three tasks respectively. This would result in a 100% utilization of Resource 2 and Resource 3; however, after the completion of Task 1, Resource 1 would be idle. This is referred to as “under-utilizing” a resource.
To avoid the generation of a flat schedule by a CPM scheduling program, the user is required to enter artificial dependency information such as links or start dates. Thus, to avoid the flat schedule shown in Schedule Example 1, the user could define the start date of Task 2 as dependent upon the completion of Task 1, and the start date of Task 3 as dependent upon the completion of Task 2. For projects with several tasks, this process may require a significant amount of effort for the user. Thus, there is a need for a scheduling program which can generate a meaningful schedule for a set of non-dependent tasks. Furthermore, there is a need for a scheduling program that can generate a meaningful schedule for a set of non-dependent tasks without requiring the input of artificial constraints such as start dates or dependencies.
A schedule in which resources are overloaded and/or under-utilized is referred to as an “unbalanced” schedule. As previously illustrated, CPM scheduling programs are susceptible to producing unbalanced schedules. One method that has been developed to address this deficiency in CPM scheduling programs is referred to as “leveling”. The leveling process operates separately from the CPM scheduling and is designed to balance the resource utilization of a schedule. In this process, an overloaded resource is identified, and the task or tasks causing the first instance of the overload are determined. Next, adjustments are made to the start and/or finish dates of the task or tasks causing the overload to reduce the resource usage to 100%. Because this adjustment may result in changing the critical path, each time a leveling adjustment is made, the critical path must be recalculated before further leveling adjustments can be performed. Thus, for each leveling adjustment, a forward pass is performed to reschedule the tasks, and a backward pass is performed to recalculate the critical path. Depending on the number of tasks and the amount of overloading, this process can require a significant amount of iterative processing which wastes valuable processor time. Thus, there is a need for a method of scheduling which produces a balanced schedule. There is also a need for a method of scheduling that efficiently and quickly produces a balanced schedule which maximizes the use of the available resources.
CPM scheduling programs operate on a task-oriented basis. A problem that results from task-oriented scheduling is the tendency to under-utilize the available resources. The following example is illustrative of this problem. If the following information is provided to a CPM scheduling program:
Resource 1 (R1) is assigned to Task 1,
Resources 1 and 2 (R1,R2) are assigned to Task 2, and
Resource 2 is assigned to Task 3,
upon completion of the scheduling process, the schedule shown in Schedule Example 1 would be created. Next, upon completion of the leveling process, a possible outcome of the schedule is shown in Schedule Example 2.
Schedule Example 2|-----Task 1 (R1)-----|          |---Task 2 (R1, R2)---|                  |-------Task 3 (R2)------|
In Schedule Example 2, Task 2 has been scheduled to start upon the completion of Task 1 and Task 3 has been scheduled to start upon the completion of Task 2. Task 2 is scheduled to begin after Task 1 in order to avoid overloading of Resource 1. This results, however, in under-utilizing Resource 2, which is not scheduled during the time Resource 1 is working on Task 1. This under-utilization occurs as a result of using task-oriented scheduling. CPM scheduling with leveling would not allow Resource 2 to be scheduled to work on Task 2 in parallel with Resource 1 working on Task 1 because that would appear to overload Resource 1.
A second possible schedule that could result from the input information provided above is shown in Scheduling Example 3.
Schedule Example 3|------Task 1 (R1)------|               |---Task 2 (R1,R2)----||------------Task 3 (R2)-------------|
In Scheduling, Example 3, Resource 2 has been scheduled to work on Task 3 in parallel with Resource 1 working on Task 1, and Task 2 has been scheduled to begin upon the completion of Task 3. In this schedule, Resource 1 is under-utilized during the time after the completion of Task 1 and prior to the start of Task 2. Again, the under-utilization occurs as a result of task-oriented scheduling. Because Resource 2 is assigned to both Task 2 and Task 3, Task 2 can not begin until the completion of Task 3.
An alternative to task-oriented scheduling is assignment-oriented scheduling. In Schedule Examples 2 and 3, Task 2 can be viewed as consisting of two assignments, one assignment for Resource 1 and another for Resource 2. By performing assignment-oriented scheduling in Schedule Example 2, Resource 2 could begin working on Task 2 in parallel with Resource 1 working on Task 1. The resulting schedule is shown in Schedule Example 4.
Schedule Example 4|------Task1(R1)------|          |------Task2(R1)------||------Task2(R2)------|          |------------Task3(R2)-------------|
Likewise, by utilizing assignment-oriented scheduling in Schedule Example 3, Resource 1 can begin work on Task 2 upon the completion of Task 1, thereby avoiding the under-utilization of Resource 1. Scheduling Example 5 illustrates a schedule that could result from use of assignment-oriented scheduling.
Schedule Example 5|------Task1(R1)------|          |------Task2(R1)-----|             |------Task2(R2)-----||------------Task3(R2)-------------|
Thus, to allow for the most efficient allocation of resources, there is a need for a method to generate a schedule which is assignment-oriented rather than task-oriented. There is also a need for a method which allows the independent scheduling of individual assignments of a task. This is illustrated in Scheduling Example 4 and 5 by splitting Task 2 into two independent assignments.
CPM scheduling programs schedule tasks linearly, which contributes to the under-utilization of resources. Linear scheduling implies that once a task is started, work must continue on that task until it is completed. Thus, in Schedule Example 2, if the start of Task 2 is dependent upon the completion of Task 1, then Resource 2 could not work on Task 2 in parallel with Task 1 as illustrated in Schedule Example 4. Thus, Resource 2 will be under-utilized. An alternative to linear scheduling is to view each task as a series of smaller assignments which can be performed independently. For example, if the duration of Task 3 is one month, then Task 3 can be viewed as four (4) one week assignments or twenty (20) one day assignments. Each of these assignments can then be independently scheduled and Schedule Example 6 could result.
Schedule Example 6|------Task1(R1)------|          |---Task2(R1, R2)----||------Task3(R2)-------|         |--Task3(R2)-|
In Schedule Example 6, Task 3 has been subdivided into two assignments. The first assignment is performed in parallel with Task 1 to avoid the under-utilization of Resource 2 during this period of time. Because CPM scheduling utilizes linear scheduling, a CPM-based scheduling program could not subdivide Task 3 as illustrated. Thus, there is a need for a scheduling method which subdivides a task or assignment into components which can be individually scheduled, and generates a maximum resource utilization schedule based on these components.
Thus, there are several problems and deficiencies associated with CPM scheduling programs. Some of these problems, such as flat scheduling, can be alleviated by burdening the user with the requirement of creating artificial constraints upon the entered tasks. Other problems, such as the under-utilization of resources can not be alleviated within the constraints of CPM scheduling. Therefore, there is a need for an efficient method of scheduling that will generate meaningful schedules which maximize resource utilization by performing assignment-oriented scheduling.